
public class Huffman {

	public static String[] caracteres;
	public String caracter;
	public int longitud;
	public int longitud2;
	public int[] frec;
	public int[] codigo;
	public String[] carac;
	public String sustituir = "$";
	public int left;
	public int right;
	public Arbol heap;
	
	
	
	public Huffman(String[] c){
		caracteres = new String[c.length];
		frec = new int[c.length];
		carac = new String[c.length];
		codigo = new int[c.length];
		caracteres= c;
		longitud = c.length;
			
	}
	

	public int[] frecuencia(){
		int pos3 = 0;
		for (int pos2=0; pos2<longitud;pos2++){
			if (caracteres[pos2] != "$"){
				caracter = caracteres[pos2];
				carac[pos3] = caracteres[pos2];
				frec[pos3]++;
				int pos = pos2;
				pos++;
				for (pos = pos ; pos<longitud; pos++){
					int comp = caracter.compareTo(caracteres[pos]);
					
					if (comp == 0){
						frec[pos3]++;
						caracteres[pos] = sustituir;
					}
				}
				pos3++;
			}
		}
		return frec;
	}
	
	
	
	public String[] getLetras(){
		return carac;
	}
	public void setletrasfrec(int[] f, String[] l){
		frec = f;
		carac = l;
	}
	
	
	
	/*public String creatarbol(int[] f){
		heap = new Arbol(f);
		for(int pos = 0; pos<longitud-1; pos++){
			if (frec[pos] != 0){
				leaf leaf1 = new leaf(carac[pos], frec[pos]);
				huffmanTree left= new huffmanTree(leaf1);
				frec[pos] = 0;
				pos++;
				leaf leaf2 = new leaf(carac[pos], frec[pos]);
				huffmanTree right= new huffmanTree(leaf2);
				
				huffmanTree tree = new huffmanTree(left, right);				
				tree.print();
				pos--;
				
				
				//print(BinaryTree r, String representation)
			}
		}
		return heap.toString();
	}
	*/
	
	public void setCodigo(){
		int numero = 0;
		for (int pos=(longitud-1); pos>=0; pos--){
			codigo[pos] = numero;
			numero++;
		}
	}


	public int[] getFrec() {
		return frec;
	}
	

	public String toString(){
		 String descripcion = ""; 
		 descripcion += "caracter  |  frecuencia  |  codigo";
		 descripcion += "\n";
		 for (int pos =0; pos<carac.length;pos++){
			 if (carac[pos] != null){
				 descripcion +="    " + carac[pos] +"\t        "+ frec[pos] + "\t     "+ codigo[pos]; 
				 descripcion += "\n";
				 }
			 }
		 descripcion += "\n";
		 return descripcion;  
	}
}

	class huffmanTree {
	    BinaryTree root; // root of tree
	    int totalWeight;     // weight of tree

	    public huffmanTree(leaf e)
	    // post: construct a leaf with associated character
	    {
		root = new BinaryTree(e);
		totalWeight = e.frequency;
	    }

	    public huffmanTree(huffmanTree left, huffmanTree right)
	    // pre: left and right non-null
	    // post: merge two trees together and merge their weights
	    {
		this.totalWeight = left.totalWeight + right.totalWeight;
		root = new BinaryTree(null,left.root,right.root);
	    }

	    public int compareTo(Object other)
	    // pre: other is non-null
	    // post: return integer reflecting relation between values
	    {
		huffmanTree that = (huffmanTree)other;
		return this.totalWeight - that.totalWeight;
	    }

	    public boolean equals(Object that)
	    // post: return true if this and that are same tree instance
	    {
		return this == that;
	    }
	    
	    public void print()
	    // post: print out strings associated with characters in tree
	    {
		print(this.root,"");
	    }

	    protected void print(BinaryTree r, String representation)
	    // post: print out strings associated with chars in tree r,
	    //       prefixed by representation
	    {
		if (!r.left().isEmpty())
		{   // interior node
		    print(r.left(),representation+"0"); // append a 0
		    print(r.right(),representation+"1"); // append a 1
		} else { // leaf; print encoding
		    leaf e = (leaf)r.value();
		    System.out.println("Encoding of "+e.ch+" is "+
		       representation+" (frequency was "+e.frequency+")");
		}
	    }
	}

	class leaf
	{
	    int frequency; // frequency of char
	    String ch;	// the character

	    public leaf(String c, int f)
	    // post: construct character entry with frequency 1
	    {
		ch = c;
		frequency = f;
	    }

	    public boolean equals(Object other)
	    // post: return true if leaves represent same character
	    {
		leaf that = (leaf)other;
		return this.ch == that.ch;
	    }
	}
	
	class BinaryTree
	{
	    /**
	     * The value associated with this node
	     */
	    protected Object val; // value associated with node
	    /**
	     * The parent of this node
	     */
	    protected BinaryTree parent; // parent of node
	    /**
	     * The left child of this node, or EMPTY
	     */
	    protected BinaryTree left, right; // children of node
	    /**
	     * The unique empty node
	     */
	    public static final BinaryTree EMPTY = new BinaryTree();

	    /**
	     * A one-time constructor, for constructing empty trees.
	     * @post Private constructor that generates the EMPTY node
	     * @return the EMPTY node
	     */
	    private BinaryTree()
	    {
		val = null;
		parent = null; left = right = this;
	    }

	    /**
	     * Constructs a tree node with no children.  Value of the node
	     * is provided by the user
	     *
	     * @post Returns a tree referencing value with two null subtrees
	     * @param value A (possibly null) value to be referenced by node
	     */
	    public BinaryTree(Object value)
	    {
		val = value;
		parent = null;
		left = right = EMPTY;
	    }

	    /**
	     * Constructs a tree node with no children.  Value of the node
	     * and subtrees are provided by the user
	     *
	     * @post Returns a tree referencing value and subtree
	     * @param value A (possibly null) value to be referenced by node
	     * @param left The subtree to be left subtree of node
	     * @param right The subtree to be right subtree of node
	     */
	    public BinaryTree(Object value, BinaryTree left, BinaryTree right)
	    {
		this(value);
		setLeft(left);
		setRight(right);
	    }

	    /**
	     * Get left subtree of current node
	     *
	     * @post Returns reference to left subtree, or null
	     *
	     * @return The left subtree of this node
	     */
	    public BinaryTree left()
	    {
		return left;
	    }

	    /**
	     * Get right subtree of current node
	     *
	     * @post Returns reference to right subtree, or null
	     * 
	     * @return The right subtree of this node
	     */
	    public BinaryTree right()
	    {
		return right;
	    }

	    /**
	     * Get reference to parent of this node
	     *
	     * @post Returns reference to parent node, or null
	     * 
	     * @return Reference to parent of this node
	     */
	    public BinaryTree parent()
	    {
		return parent;
	    }
	    
	    /**
	     * Update the left subtree of this node.  Parent of the left subtree
	     * is updated consistently.  Existing subtree is detached
	     *
	     * @post Sets left subtree to newLeft
	     *       re-parents newLeft if not null
	     * 
	     * @param newLeft The root of the new left subtree
	     */
	    public void setLeft(BinaryTree newLeft)
	    {
		if (isEmpty()) return;
		if (left.parent() == this) left.setParent(null);
		left = newLeft;
		left.setParent(this);
	    }

	    /**
	     * Update the right subtree of this node.  Parent of the right subtree
	     * is updated consistently.  Existing subtree is detached
	     *
	     * @post Sets left subtree to newRight
	     *       re-parents newRight if not null
	     * 
	     * @param newRight A reference to the new right subtree of this node
	     */
	    public void setRight(BinaryTree newRight)
	    {
		if (isEmpty()) return;
		if (right.parent() == this) right.setParent(null);
		right = newRight;
		right.setParent(this);
	    }

	    /**
	     * Update the parent of this node
	     *
	     * @post Re-parents this node to parent reference, or null
	     *
	     * @param newParent A reference to the new parent of this node
	     */
	    protected void setParent(BinaryTree newParent)
	    {
		parent = newParent;
	    }

	    /**
	     * Returns the number of descendants of node
	     *
	     * @post Returns the size of the subtree
	     * @return Size of subtree
	     */
	    public int size()
	    {
		if (isEmpty()) return 0;
		return left().size() + right().size() + 1;
	    }

	    /**
	     * Returns reference to root of tree containing n
	     *
	     * @post Returns the root of the tree node n
	     * @return Root of tree
	     */
	    public BinaryTree root()
	    {
		if (parent() == null) return this;
		else return parent().root();
	    }

	    /**
	     * Returns height of node in tree.  Height is maximum path
	     * length to descendant
	     *
	     * @post Returns the height of a node in its tree
	     * @return The height of the node in the tree
	     */
	    public int height()
	    {
		if (isEmpty()) return -1;
		return 1 + Math.max(left.height(),right.height());
	    }

	    /**
	     * Compute the depth of a node.  The depth is the path length
	     * from node to root
	     *
	     * @post Returns the depth of a node in the tree
	     * @return The path length to root of tree
	     */
	    public int depth()
	    {
		if (parent() == null) return 0;
		return 1 + parent.depth();
	    }

	    /**
	     * Returns true if tree is full.  A tree is full if adding a node
	     * to tree would necessarily increase its height
	     *
	     * @post Returns true iff the tree rooted at node is full
	     * @return True iff tree is full
	     */
	    public boolean isFull()
	    {
		if (isEmpty()) return true;
		if (left().height() != right().height()) return false;
		return left().isFull() && right().isFull();
	    }

	    /**
	     * Returns true if tree is empty.
	     * @post Returns true iff the tree rooted at node is empty
	     * @return True iff tree is empty
	     */
	    public boolean isEmpty()
	    {
		return this == EMPTY;
	    }
	    
	    /**
	     * Return whether tree is complete.  A complete tree has minimal height
	     * and any holes in tree would appear in last level to right.	
	     *
	     * @post Returns true iff the tree rooted at node is complete
	     * @return True iff the subtree is complete
	     */
	    public boolean isComplete()
	    {
		int leftHeight, rightHeight;
		boolean leftIsFull, rightIsFull;
		boolean leftIsComplete, rightIsComplete;
		if (isEmpty()) return true;
		leftHeight = left().height();
		rightHeight = right().height();
		leftIsFull = left().isFull();
		rightIsFull = right().isFull();
		leftIsComplete = left().isComplete();
		rightIsComplete = right().isComplete();

		// case 1: left is full, right is complete, heights same
		if (leftIsFull && rightIsComplete &&
		    (leftHeight == rightHeight)) return true;
	        // case 2: left is complete, right is full, heights differ
		if (leftIsComplete && rightIsFull &&
		    (leftHeight == (rightHeight + 1))) return true;
		return false;
	    }

	    /**
	     * Return true iff the tree is height balanced.  A tree is height
	     * balanced iff at every node the difference in heights of subtrees is
	     * no greater than one
	     *
	     * @post Returns true iff the tree rooted at node is balanced
	     * @return True if tree is height balanced
	     */
	    public boolean isBalanced()
	    {
		if (isEmpty()) return true;
		return (Math.abs(left().height()-right().height()) <= 1) &&
		       left().isBalanced() && right().isBalanced();
	    }

	    

	    

	 
	    /**
	     * Method to perform a right rotation of tree about this node
	     * Node must have a left child.  Relation between left child and node
	     * are reversed
	     *
	     * @pre This node has a left subtree
	     * @post Rotates local portion of tree so left child is root
	     */
	    protected void rotateRight()
	    {
		BinaryTree parent = parent();
		BinaryTree newRoot = left();
		boolean wasChild = parent != null;
		boolean wasLeftChild = isLeftChild();

		// hook in new root (sets newRoot's parent, as well)
	        setLeft(newRoot.right());

		// puts pivot below it (sets this's parent, as well)
	        newRoot.setRight(this);

		if (wasChild) {
		    if (wasLeftChild) parent.setLeft(newRoot);
		    else              parent.setRight(newRoot);
		}
	    }

	    /**
	     * Method to perform a left rotation of tree about this node
	     * Node must have a right child.  Relation between right child and node
	     * are reversed
	     *
	     * @pre This node has a right subtree
	     * @post Rotates local portion of tree so right child is root
	     */
	    protected void rotateLeft()
	    {
		// all of this information must be grabbed before
		// any of the references are set.  Draw a diagram for help
		BinaryTree parent = parent();
		BinaryTree newRoot = right();
		// is the this node a child; if so, a left child?
		boolean wasChild = parent != null;
		boolean wasRightChild = isRightChild();

		// hook in new root (sets newRoot's parent, as well)
	        setRight(newRoot.left());

		// put pivot below it (sets this's parent, as well)
	        newRoot.setLeft(this);

		if (wasChild) {
		    if (wasRightChild) parent.setRight(newRoot);
		    else               parent.setLeft(newRoot);
		}
	    }

	    /**
	     * Determine if this node is a left child
	     *
	     * @post Returns true if this is a left child of parent
	     * 
	     * @return True iff this node is a left child of parent
	     */
	    public boolean isLeftChild()
	    {
		if (parent() == null) return false;
		return this == parent().left();
	    }

	    /**
	     * Determine if this node is a right child
	     *
	     * @post Returns true if this is a right child of parent
	     * 
	     * @return True iff this node is a right child of parent
	     */
	    public boolean isRightChild()
	    {
		if (parent() == null) return false;
		return this == parent().right();
	    }

	    /**
	     * Returns value associated with this node
	     *
	     * @post Returns value associated with this node
	     * 
	     * @return The node's value
	     */
	    public Object value()
	    {
		return val;
	    }

	    /**
	     * Set's value associated with this node
	     *
	     * @post Sets the value associated with this node
	     * @param value The new value of this node
	     */
	    public void setValue(Object value)
	    {
		val = value;
	    }

	    /**
	     * @post return sum of hashcodes of the contained values
	     */
	    public int hashCode()
	    {
		if (isEmpty()) return 0;
		int result = left().hashCode() + right().hashCode();
		if (value() != null) result += value().hashCode();
		return result;
	    }
	    
	    /**
	     * Returns a string representing the tree rooted at this node.
	     * <font color="#FF0000">WARNING</font> this can be a very long string.
	     * 
	     * @return A string representing the tree rooted at this node.
	     */
	    public String treeString(){
		String s = "";
		for (int i=0; i < this.depth(); i++){
		    s += "\t|";
		}
		
		s += ("<" + val + " : " + getHand() + ">\n");
		
		if (left  != EMPTY) s += left.treeString();
		if (right != EMPTY) s += right.treeString();

		return s;
	    }
	    
	    /**
	     * Support method for {@link #toString}. Returns R if this is node 
	     * is a right child, L if this node is a left child and Root if this
	     * node is the root.
	     * 
	     * @return R if this is node 
	     * is a right child, L if this node is a left child and Root if this
	     * node is the root.
	     */
	    private String getHand(){
		if (isRightChild()) return "R";
		if (isLeftChild()) return "L";
		return "Root";	
	    }
	    
	    
	    /**
	     * Returns a representation the subtree rooted at this node
	     *
	     * @post Returns string representation
	     * 
	     * @return String representing this subtree
	     */
	    public String toString()
	    {
		if (isEmpty()) return "<BinaryTree: empty>";
		StringBuffer s = new StringBuffer();
		s.append("<BinaryTree "+value());
		if (!left().isEmpty()) s.append(" "+left());
		else s.append(" -");
		if (!right().isEmpty()) s.append(" "+right());
		else s.append(" -");
		s.append('>');
		return s.toString();
	    }
	}


